#include <stdio.h>
#include <stdlib.h>
#include <conio.h> // 用于 getch() 函数

// 树存储结构
typedef struct BiTNode {
	char data;
	struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;

// 循环队列算法，辅助完成二叉树层次遍历
#define MaxSize 50 // 定义队列中元素的最大个数

typedef struct {
	BiTree data[MaxSize]; // 存放队列元素
	int front, rear;      // 队头和队尾指针
} SqQueue;

// 初始化队列（带头结点）
void Queue_Init(SqQueue &Q) {
	Q.rear = Q.front = 0;
}

// 判断队列是否为空
bool Queue_Empty(SqQueue Q) {
	return Q.front == Q.rear;
}

// 入队
bool Queue_En(SqQueue &Q, BiTree e) {
	if ((Q.rear + 1) % MaxSize == Q.front)
		return false; // 队满则报错
	Q.data[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MaxSize; // 队尾指针加 1 取模
	return true;
}

// 出队
bool Queue_De(SqQueue &Q, BiTree &e) {
	if (Queue_Empty(Q))
		return false; // 队空则报错
	e = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	return true;
}

// 通过给定数组创建二叉树，0为空结点
// nums 为数组、len 为数组长度、i 为当前数组下标
BiTNode *BiTree_Create(char *nums, int len, int i) {
	if (i >= len || nums[i] == '\0')
		return NULL; // 使用'\0'表示空结点
	BiTNode *node = (BiTNode *)malloc(sizeof(BiTNode));
	node->data = nums[i];
	node->lchild = BiTree_Create(nums, len, 2 * i + 1);
	node->rchild = BiTree_Create(nums, len, 2 * i + 2);
	return node;
}

// 先序遍历: 根左右(NLR)
void Order_Pre(BiTree tree) {
	if (tree == NULL)
		return;
	printf("%c,", tree->data); // 访问根树内容
	Order_Pre(tree->lchild);   // 递归遍历左子树
	Order_Pre(tree->rchild);   // 递归遍历右子树
}

// 中序遍历: 左根右(LNR)
void Order_In(BiTree tree) {
	if (tree == NULL)
		return;
	Order_In(tree->lchild);    // 递归遍历左子树
	printf("%c,", tree->data); // 访问根树内容
	Order_In(tree->rchild);    // 递归遍历右子树
}

// 后序遍历: 左右根(LRN)
void Order_Post(BiTree tree) {
	if (tree == NULL)
		return;
	Order_Post(tree->lchild);  // 递归遍历左子树
	Order_Post(tree->rchild);  // 递归遍历右子树
	printf("%c,", tree->data); // 访问根树内容
}

// 层次遍历
void Order_Level(BiTree tree) {
	SqQueue Q; // 初始化队列
	Queue_Init(Q);
	BiTree p;
	Queue_En(Q, tree); // 根节点入队

	while (!Queue_Empty(Q)) {
		// 队列不空则继续遍历
		Queue_De(Q, p);         // 队头结点出队
		printf("%c,", p->data); // 访问出队结点内容
		if (p->lchild != NULL)
			Queue_En(Q, p->lchild); // 左子树不为空，则左子树根入队
		if (p->rchild != NULL)
			Queue_En(Q, p->rchild); // 右子树不为空，则右子树根入队
	}
}

// 插入节点
bool InsertNode(BiTree &tree, char data) {
	printf("插入节点 %c\n", data);

	if (tree == NULL) {
		tree = (BiTNode *)malloc(sizeof(BiTNode));
		printf("null插入节点 %c\n", data);
		tree->data = data;
		tree->lchild = tree->rchild = NULL;
		return true;

	} else if (data < tree->data) {
		return InsertNode(tree->lchild, data);

	} else if (data > tree->data) {
		return InsertNode(tree->rchild, data);
	}
	return false; // 数据已存在，不插入
}

// 统计二叉树的节点个数
int CountNodes(BiTree tree) {

	if (tree == NULL) {
		return 0; // 空树节点数为0

	} else {
		return 1 + CountNodes(tree->lchild) + CountNodes(tree->rchild); // 根节点加上左右子树的节点数
	}
}

// 统计二叉树的叶子节点个数
int CountLeaves(BiTree tree) {
	if (tree == NULL) {
		return 0; // 空树叶子节点数为0
	} else if (tree->lchild == NULL && tree->rchild == NULL) {
		return 1; // 叶子节点返回1
	} else {
		return CountLeaves(tree->lchild) + CountLeaves(tree->rchild); // 左右子树的叶子节点数之和
	}
}

// 释放节点内存
void FreeTree(BiTree &tree) {
	if (tree == NULL)
		return;
	FreeTree(tree->lchild);
	FreeTree(tree->rchild);
	free(tree);
	tree = NULL;
}

// 计算二叉树高度
int TreeHeight(BiTree tree) {
	if (tree == NULL)
		return 0;
	int lHeight = TreeHeight(tree->lchild);
	int rHeight = TreeHeight(tree->rchild);
	return (lHeight > rHeight ? lHeight : rHeight) + 1;
}

// 动态创建二叉树
void CreateBiTree(BiTree *tree) {
	char data;
	printf("请输入节点数据（输入'\\0'表示空节点，输入'0'结束创建）：");
	scanf(" %c", &data); // 读取字符，注意前面的空格用于跳过空白字符

	if (data == '\0' || data == '0') {
		*tree = NULL;
	} else {
		*tree = (BiTNode *)malloc(sizeof(BiTNode));

		if (!*tree) {
			perror("内存分配失败");
			exit(EXIT_FAILURE);
		}
		(*tree)->data = data;
		printf("创建 %c 的左子树\n", data);
		CreateBiTree(&((*tree)->lchild)); // 递归创建左子树
		printf("创建 %c 的右子树\n", data);
		CreateBiTree(&((*tree)->rchild)); // 递归创建右子树
	}
}

typedef struct LinkStack {
	BiTNode **elements;
	int top;
	int maxSize;
} LinkStack;

void InitStack(LinkStack *S, int size) {
	S->elements = (BiTNode **)malloc(sizeof(BiTNode *) * size);
	S->top = -1;
	S->maxSize = size;
}

int IsEmpty(LinkStack S) {
	return S.top == -1;
}

void Push(LinkStack *S, BiTNode *node) {
	if (S->top < S->maxSize - 1) {
		S->elements[++S->top] = node;
	}
}

BiTNode *Pop(LinkStack *S) {
	if (!IsEmpty(*S)) {
		return S->elements[S->top--];
	}
	return NULL;
}

BiTNode *SearchNodeIterative(BiTree tree, char data) {
	LinkStack S;
	InitStack(&S, 100);
	BiTNode *current = tree;
	BiTNode *temp = NULL;

	while (current != NULL || !IsEmpty(S)) {
		while (current != NULL) {
			printf("当前节点数据：%c\n", current->data);
			if (current->data == data) {
				printf("找到节点：%c\n", data);
				temp = current;
				goto end; // 找到节点后跳转到函数末尾
			}
			Push(&S, current);
			if (data < current->data) {
				current = current->lchild;
			} else {
				current = current->rchild;
			}
		}
		if (!IsEmpty(S)) {
			current = Pop(&S);
			printf("回退到节点：%c\n", current->data);
			if (data < current->data) {
				current = current->rchild;
			} else {
				current = current->lchild;
			}
		}
	}

end:
	return temp; // 返回找到的节点
}

void DeleteNode(BiTree *tree, char data) {
	if (tree == NULL || *tree == NULL) {
		return; // 空树或空节点，直接返回
	}
	// 查找要删除的结点
	BiTNode *toDelete = SearchNodeIterative(*tree, data);

	if (toDelete != NULL) {
		printf("删除节点：%c\n", toDelete->data);
		BiTNode *parent = NULL; // 要删除节点的父节点
		BiTNode *temp = NULL; // 用于替换的子节点

		// 回溯找到父节点
		BiTNode *current = *tree;
		LinkStack S;
		InitStack(&S, 100); // 假设栈的最大大小为100
		while (current != toDelete && current != NULL) {
			Push(&S, current);
			if ((current->lchild && current->lchild == toDelete) || (current->rchild && current->rchild == toDelete)) {
				parent = current;
			}
			if (current->lchild == toDelete) {
				current = current->lchild;
			} else if (current->rchild == toDelete) {
				current = current->rchild;
			} else {
				current = (current->data < data) ? current->rchild : current->lchild;
			}
		}

		// 情况1: 要删除的节点没有子节点（叶子节点）
		if (toDelete->lchild == NULL && toDelete->rchild == NULL) {
			if (parent->lchild == toDelete) {
				parent->lchild = NULL;
			} else {
				parent->rchild = NULL;
			}
			free(toDelete);
		}
		// 情况2: 要删除的节点有一个子节点
		else if (toDelete->lchild != NULL && toDelete->rchild == NULL ||
		         toDelete->lchild == NULL && toDelete->rchild != NULL) {
			temp = (toDelete->lchild != NULL) ? toDelete->lchild : toDelete->rchild;
			if (parent->lchild == toDelete) {
				parent->lchild = temp;
			} else {
				parent->rchild = temp;
			}
			free(toDelete);
		}
		// 情况3: 要删除的节点有两个子节点
		else {
			BiTNode *successor = toDelete->rchild;
			while (successor->lchild != NULL) {
				successor = successor->lchild; // 找到右子树中的最小节点
			}
			// 将后继节点的值复制到要删除的节点
			toDelete->data = successor->data;
			// 删除后继节点
			DeleteNode(&successor, successor->data); // 递归删除后继节点
		}
	} else {
		printf("没有该节点");
	}
}

// 显示菜单函数
void ShowMenu() {
	printf("  == 二叉树操作菜单 ==         1. 创建二叉树    \n");
	printf("2. 先序遍历    3. 中序遍历    4. 后序遍历    5. 层次遍历\n");
	printf("6. 插入节点    7. 删除节点    8. 查找节点    9. 计算树高\n");
	printf("10. 统计节点个数    11. 统计叶子节点个数     0. 退出程序\n");
	printf("请选择操作：");
}

// 主函数
int main() {
	BiTree tree = NULL; // 初始化二叉树为空
	int choice;
	char data;
	BiTNode *found = NULL; // 将 found 声明移到 switch 之外

	while (1) {
		ShowMenu(); // 显示菜单

		if (scanf("%d", &choice) != 1) {
			printf("输入无效，请输入数字。\n");
			while (getchar() != '\n')
				; // 清空输入缓冲区
			continue;
		}

		switch (choice) {
			case 1:
				CreateBiTree(&tree);
				// 创建二叉树的代码
				break;
			case 2:
				// 先序遍历的代码
				Order_Pre(tree);
				printf("\n");
				break;
			case 3:
				// 中序遍历的代码
				Order_In(tree);
				printf("\n");
				break;
			case 4:
				// 后序遍历的代码
				Order_Post(tree);
				printf("\n");
				break;
			case 5:
				// 层次遍历的代码
				Order_Level(tree);
				printf("\n");
				break;
			case 6:
				// 插入节点
				printf("请输入要插入的数据：");
				scanf(" %c", &data);
				InsertNode(tree, data);
				break;
			case 7:
				// 删除节点
				printf("请输入要删除的数据：");
				scanf(" %c", &data);
				DeleteNode(&tree, data);
				break;
			case 8:
				// 查找节点
				printf("请输入要查找的数据：");
				scanf(" %c", &data);
				found = SearchNodeIterative(tree, data);
				if (found != NULL) {
					printf("找到节点，数据为：%c\n", found->data);
				} else {
					printf("未找到节点。\n");
				}
				break;
			case 9:
				// 计算树高
				printf("树的高度为：%d\n", TreeHeight(tree));
				break;
			case 0:
				// 退出程序
				FreeTree(tree);
				printf("程序已退出。\n");
				return 0;
			case 10:
				// 统计节点个数
				printf("二叉树的节点个数为：%d\n", CountNodes(tree));
				break;
			case 11:
				// 统计叶子节点个数
				printf("二叉树的叶子节点个数为：%d\n", CountLeaves(tree));
				break;
			default:
				printf("无效的选择，请重新输入。\n");
		}
		while (getchar() != '\n')
			; // 清空输入缓冲区
	}
	return 0;
}